package 数据结构和算法.数据结构.普通二叉树.二叉查找树;

import 数据结构和算法.数据结构.普通二叉树.TreeNode;

public class DynamicTree {
    public static void main(String[] args) {
        int[] array = {10, 9, 20, 15, 35};

        // 创建树
        TreeRoot treeRoot = new TreeRoot();
        for (int i = 0; i < array.length; ++i) {
            createTree(treeRoot, array[i]);
        }

        // 前序遍历
        //preTraverseBTree(treeRoot.getRootNode());

        // 中序遍历
        //inTraverseBTree(treeRoot.getRootNode());

        // 后序遍历
        afterTraverseBTree(treeRoot.getRootNode());

        System.out.println("深度：" + getHeight(treeRoot.getRootNode()));

        System.out.println("最大值：" + getMax(treeRoot.getRootNode()));

        System.out.println("<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>");

        // 构造一棵树
        TreeNode treeNode = new TreeNode(10);
        TreeNode treeNode1 = new TreeNode(9);
        TreeNode treeNode2 = new TreeNode(20);
        TreeNode treeNode3 = new TreeNode(15);
        TreeNode treeNode4 = new TreeNode(35);

        treeNode.setLeftTreeNode(treeNode1);
        treeNode.setRightTreeNode(treeNode2);
        treeNode2.setLeftTreeNode(treeNode3);
        treeNode2.setRightTreeNode(treeNode4);

        // 调用前序遍历
        //preTraverseBTree(treeNode);

        // 中序遍历
        //inTraverseBTree(treeNode);

        // 后序遍历
        afterTraverseBTree(treeNode);
    }

    static class TreeRoot {
        private TreeNode rootNode;

        public TreeRoot() {
        }

        public TreeNode getRootNode() {
            return rootNode;
        }

        public void setRootNode(TreeNode rootNode) {
            this.rootNode = rootNode;
        }
    }

    public static void createTree(TreeRoot treeRoot, int value) {
        // 如果根节点不存在
        if (treeRoot.getRootNode() == null) {
            treeRoot.setRootNode(new TreeNode(value));
        } else {
            TreeNode tempNode = treeRoot.getRootNode();
            while (tempNode != null) {
                if (value <= tempNode.getValue()) {
                    if (tempNode.getLeftTreeNode() == null) {
                        tempNode.setLeftTreeNode(new TreeNode(value));
                        return;
                    } else {
                        tempNode = tempNode.getLeftTreeNode();
                    }
                } else {
                    if (tempNode.getRightTreeNode() == null) {
                        tempNode.setRightTreeNode(new TreeNode(value));
                        return;
                    } else {
                        tempNode = tempNode.getRightTreeNode();
                    }
                }
            }
        }
    }

    // 前序遍历
    public static void preTraverseBTree(TreeNode rootNode) {
        if (rootNode != null) {
            System.out.println(rootNode.getValue());

            preTraverseBTree(rootNode.getLeftTreeNode());

            preTraverseBTree(rootNode.getRightTreeNode());
        }
    }

    // 中序遍历
    private static void inTraverseBTree(TreeNode rootNode) {
        if (rootNode != null) {
            inTraverseBTree(rootNode.getLeftTreeNode());

            System.out.println(rootNode.getValue());

            inTraverseBTree(rootNode.getRightTreeNode());
        }
    }

    // 后序遍历
    private static void afterTraverseBTree(TreeNode rootNode) {
        if (rootNode != null) {
            afterTraverseBTree(rootNode.getLeftTreeNode());

            afterTraverseBTree(rootNode.getRightTreeNode());

            System.out.println(rootNode.getValue());
        }
    }

    // 获取深度
    public static int getHeight(TreeNode treeNode) {
        if (null == treeNode) {
            return 0;
        } else {
            int left = getHeight(treeNode.getLeftTreeNode());

            int right = getHeight(treeNode.getRightTreeNode());

            if (left >= right) {
                return left + 1;
            } else {
                return right + 1;
            }
        }
    }

    // 获取最大值
    public static int getMax(TreeNode treeNode) {
        if (treeNode == null) {
            return -1;
        } else {
            int left = getMax(treeNode.getLeftTreeNode());

            int right = getMax(treeNode.getRightTreeNode());

            int cuurValue = treeNode.getValue();

            int max = left;
            if (max < right) {
                max = right;
            }

            if (cuurValue > max) {
                max = cuurValue;
            }

            return max;
        }
    }
}
